A forwarding information base (FIB) is to provide, in data communication, a network device (for example, a bridge, a switch, or a router) with an information base for forwarding a data packet to a destination address. The forwarding information base is stored in a network processor (NP) of network hardware. Reference may be made to FIG. 1 for a schematic structural diagram of the forwarding information base. The FIB uses a binary search tree (Btree) structure, where each non-empty node is corresponding to one FIB entry. In the Btree structure, except nodes in the last branch, nodes in other branches may be referred to as non-leaf nodes and are used to store keywords (Key), for example, Internet Protocol (IP) addresses, and the nodes in the last branch may be referred to as leaf nodes and are used to store associated data (AD) corresponding to the non-leaf nodes, for example, next-hop IP addresses or port numbers, so as to forward a data packet to a next-hop network device according to the FIB and a destination address in the data packet.
Generally, some FIB entries are stored in an on-chip memory of the network processor, and the other entries including the leaf nodes are stored in an off-chip memory of the network processor. Some consecutive branches in the Btree that are stored in the on-chip memory or the off-chip memory may be one stage. For example, two consecutive branches may be one stage, or three consecutive branches may be one stage. Referring to the schematic structural diagram shown in FIG. 1, the off-chip memory may store n+1 stages with sequence numbers being from 0 to n. In any stage, F nodes in the stage are stored in storage space corresponding to a same storage address, and the F nodes may be referred to as one node block. As shown in FIG. 1, there may be a plurality of node blocks in one stage. In any stage, node blocks may be numbered from right to left, where the sequence number may be referred to as a row address of a node block. A storage address of any node block is corresponding to one row address of the node block.
When a Key and its corresponding AD in the FIB need to be modified because of a change in a network topology due to addition or removal of a network device, nodes of each stage need to be read and written and responses need to be returned. A maintenance operation sequence exists between a Key and AD: When a Key to be modified and its corresponding AD are not in a same stage, a central processing unit (CPU) of a network device first sends, to the NP, a write AD request that carries a tag and is used to modify the AD, for example, a write AD request that carries a post tag, and then sends a write Key request that does not carry a post tag and is used to modify the Key. The post tag may be used to indicate that a stage n is temporarily not read and written according to the write AD request after a stage (n−1) has been read and written, but the write AD request is temporarily saved after a response to the write AD request is returned to notify the NP that the stage (n−1) has been read and written, so as to wait for completely executing, according to the write Key request, an operation of modifying the Key, and the write AD request is triggered to execute modification of AD in the stage n only after the stage (n−1) has been read and written and a response to the write Key request is returned to notify the NP that the stage (n−1) has been read and written, so that both Key modification and AD modification are executed in a process in which a Btree is read and written according to the write Key request.
Generally, because of a low processing speed of the off-chip memory and a long period for a single search for the FIB, a cache may be added between the NP and the off-chip memory to solve the problem of a low processing speed of the off-chip memory.
After the cache is added, when any off-chip stage is read and written, a command sent by a CPU of a network device needs to be sent to the off-chip memory using the cache. There is a plurality of first-in-first-out message queues in the cache, commands for performing operations on nodes corresponding to a row address of a same node block are stored in a same message queue, and commands in different message queues are scheduled in turn according to a scheduling mechanism, and responses are returned to a processor of the NP, so as to notify the processor of the NP that a current stage has been read and written. A command corresponding to a row address of a same node block indicates that the command is a command for nodes in a node block corresponding to the row address. When a Key to be modified and its corresponding AD are not in a same stage and a row address of a node block on which the Key is located is different from a row address of a node block on which the AD is located, a write Key request and a write AD request are not in a same message queue. If a message queue in which the write Key request is located is scheduled before a message queue in which the write AD request is located, it is possible that a response to the write Key request after a current stage has been read and written is returned before a response to the write AD request after the current stage has been read and written. Certainly, it is also possible that a response to the write Key request after a stage (n−1) has been read and written is returned before a response to the write AD request after the stage (n−1) has been read and written. Therefore, the response to the write Key request returned after the stage (n−1) has been read and written cannot be used to trigger the write AD request to modify AD in the stage n, and Key modification and AD modification cannot be executed in a same process in which a Btree is read and written according to the write Key request. As a result, in terms of time, a modified Key and AD that has not been modified are found according to a route search request sent after the write Key request. That is, in a case in which a Key and its corresponding AD cannot be modified synchronously, a Key and AD in a route search result do not match, so that an error in the route search result occurs, thereby causing an error in data packet forwarding.